/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.yonsei.iwb.smarttv.querygraph.algorithm;

import edu.yonsei.iwb.smarttv.model.ConceptualGraph;
import edu.yonsei.iwb.smarttv.model.ResourceNode;
import java.util.Vector;

/**
 *
 * @author DK
 */
public class GenerateSpanningTreeAlgorithm {
    
    public Vector<ConceptualGraph> generateSpanningTree(ConceptualGraph cg){
        Vector<ConceptualGraph> cg_set = new Vector<ConceptualGraph>();
        Vector<ResourceNode> nodeSet = this.getNodeSet(cg);
        int nodeSize = nodeSet.size();        
        int arcSize = cg.size();  //cg의 아크 갯수           
        int selectionNumber = nodeSize-1; //선택할 아크의 갯수(노드갯수 - 1)
        Vector<Vector<Integer>> arcCombination = new Vector<Vector<Integer>>();
        arcCombination = this.getCutPointCombination(arcSize, arcCombination, selectionNumber);
        for(int j = 0; j < arcCombination.size(); j++){
            ConceptualGraph sub_cg = new ConceptualGraph();
            for(int k = 0; k <arcCombination.get(j).size(); k++){
                int num = arcCombination.get(j).get(k);
                sub_cg.add(cg.get(num-1));
            }
            Vector<ResourceNode> tempNodeSet = getNodeSet(sub_cg);            
            if(tempNodeSet.size() == nodeSet.size()){                
                cg_set.add(sub_cg);
            }            
        }        
//        cg_set.add(cg);
        return cg_set;        
    }
    
    
    /**
     * Conceptual Graph에 있는 노드들의 집합
     * 
     * @param cg Conceptual Graph
     * @return ResourceNode의 Vector
     */
    private Vector<ResourceNode> getNodeSet(ConceptualGraph cg){
        Vector<ResourceNode> nodeSet = new Vector<ResourceNode>();
        for(int i = 0; i < cg.size(); i++){
            ResourceNode head = cg.get(i).getHead();
            ResourceNode tail = cg.get(i).getTail();
            if(!nodeSet.contains(head)){
                nodeSet.add(head);
            }
            if(!nodeSet.contains(tail)){
                nodeSet.add(tail);
            }
        }
        return nodeSet;
    }
    
    private void doExpandCombination(Vector<Integer> cutpoint, boolean[] used, int selectionNumber, int startIndex, Vector<Vector<Integer>> result) {
        if (selectionNumber == 0) {
            Vector<Integer> s = new Vector<Integer>();
            for (int i = 0; i < used.length; i++) {
                if (used[i]) {
                    s.add(cutpoint.get(i));
                }
            }
            result.add(s);
            return;
        }
        for (int i = startIndex; i <= cutpoint.size() - selectionNumber; i++) {
            used[i] = true;
            doExpandCombination(cutpoint, used, selectionNumber - 1, i + 1, result);
            used[i] = false;
        }
    }

    private Vector<Vector<Integer>> getCutPointCombination(int size, Vector<Vector<Integer>> result, int index) {
        Vector<Integer> cutpoint = new Vector<Integer>();
        for (int c = 1; c < size + 1; c++) {
            cutpoint.add(c);
        }
        boolean[] used = new boolean[size];
        doExpandCombination(cutpoint, used, index, 0, result);        
        return result;
    }
}
